

/**
 * 
 * RBTree
 * 
 * An implementation of a Red Black Tree with
 * non-negative, distinct integer values
 * 
 * ******************PUBLIC OPERATIONS*********************
 * Boolean empty()         --> check if the tree empty   
 * contains(int key)       --> check if this key is in the tree
 * void insert(int key)     --> insert a new node with this key and return number of steps
 * void delete(int key)     --> delete the node with this key and return number of steps
 * int min()               --> Return smallest key in this tree
 * int max()               --> Return largest key in this tree
 * int[] toIntArray()      --> Return an ordered array of all keys in this tree
 * int size()              --> Return the number of nodes in this tree
 * boolean isValid()	   --> Returns true if and only if the tree is a valid red-black tree
 * int maxDepth()		   --> Returns the maximum depth of a node in the tree
 * int minLeafDepth()	   --> Returns the minimum depth of a leaf in the tree
 * 
 * ********************************************************
 * 
 */

public class RBTree {
	private RBNode root;     //root of the tree 
	private int size;        //number of nodes in the tree
	
	private int i;           /* index of the toIntArray function, *
	 					      * index where to save next value    */

	private String name = "new empty tree";

	
	public String getName() {
		return name;
	}


	public void setName(String name) {
		this.name = name;
	}


	/**
	 * Tree constructor
	 * Sets tree root to be NIL node 
	 * Sets size = 0
	 * Sets toIntArray()'s index to 0
	 */
	public RBTree() {
		this.root = RBNode.nil;
		this.size = 1;
		this.i = 0;
	}
	

  /**
   * public boolean empty()
   * 
   * @return: true iff the tree is empty
   * @preconditions: none
   * @postcondition: return true iff the data structure does not contain any node
   */
  public boolean empty() {
    return root == RBNode.nil;
  }

  
  /**
   * public boolean contains(int key)
   * 
   * returns true if and only if the tree contains key
   *  
   * preconditions: none
   * postcondition: returns true iff key is in the tree
   */
  public boolean contains(int key){
	    return Search(key) != RBNode.nil;

  }
	/**
	 * private RBNode Search(int key)
	 * 
	 * search of a given key in this tree and @returns it's node. if the key is not in this tree 
	 * 						then @return nil node
	 *  
	 * @param key: key to search
	 * @preconditions: none
	 * @postcondition: if there's a node in this tree with this key then @return the node, 
	 * 						else @return nil node
	 */
	private RBNode Search(int key) {
		RBNode tree = root;
		while (tree != RBNode.nil && tree.key != key) {
			if (key < tree.key)
				tree = tree.left;
			else
				tree = tree.right;
		}
		return tree;
	}
	
	
	
	/**
	   * public void insert(int key)
	   *
	   * this method creates a new node with this key and inserts it into the tree.
	   * the method must keep this tree valid (keep its invariants).
	   * 
	   * When inserting a new value, we first insert it into the tree as we would into an ordinary binary search tree.
	   * we find the place in the tree where the new node belongs, 
	   * then attach a newly created red node containing the value
	   *  
	   * precondition:  key >= 0; contains(key) == false
	   * postcondition: contains(key) == true; this tree is a red-black-tree
	   */
	public void insert(int key) {
		RBNode x = new RBNode(key);
	    treeInsert(x);
		x.color= Color.RED;
		while (x !=root   &&  x.parent.color == Color.RED) {
			if (x.parent == x.parent.parent.left) {
				RBNode y = x.parent.parent.right;
				if (y.color == Color.RED) {
					x.parent.color = Color.BLACK;
					y.color = Color.BLACK;
					x.parent.parent.color = Color.RED;
					x = x.parent.parent;
				}else {
					if (x == x.parent.right) {
						x = x.parent;
						LeftRotate(x);
					}
					x.parent.color = Color.BLACK;
					x.parent.parent.color = Color.RED;
					RightRotate(x.parent.parent);
				}
			}
			else {
				RBNode y = x.parent.parent.left;
				if (y.color == Color.RED) {
					x.parent.color = Color.BLACK;
					y.color = Color.BLACK;
					x.parent.parent.color = Color.RED;
					x = x.parent.parent;
				}
				else {
					if (x == x.parent.left) {
						x = x.parent;
						RightRotate(x);
					}
					x.parent.color = Color.BLACK;
					x.parent.parent.color = Color.RED;
					LeftRotate(x.parent.parent);
				}
			}
		}
		
		root.color = Color.BLACK;
		size++;
	}

   /** 
     * private void treeInsert(RBNode z)
     * 
	 * this is a binary-search-tree insert method. 
	 * it inserts this key to this tree, according to the algorithm in the book 
	 * "Introduction to Algorithms" by Thomas H. Corman
	 * 
	 * @param: z: a new node to insert to this tree
	 * @preconditions: node.key >= 0; this.contains(z.key) == false 
	 * @postconditions: this.contains(z.key) == true; this tree is a binary-search-tree;
	 */
	private void treeInsert(RBNode z) {
		RBNode y = RBNode.nil;
		RBNode x = root;
		while (x != RBNode.nil){
			y = x;
			if (z.key < x.key)
				x = x.left;
			else
				x = x.right;
		}
		z.parent = y;
		if (y == RBNode.nil)
			root = z;
		else if (z.key < y.key)
			y.left = z;
		else
			y.right = z;
	}
  
	/**
	 * A rotation changes the structure of the tree without changing the in-order order of the 
	 * sequence of values that it stores. 
	 * 
	 * @param: y: node which must be rotated
	 * @preconditions: y != NIL and y.left != NIL
	 * @postconditions: this tree is a valid red-black tree
	 * 
	 */
	private void RightRotate(RBNode x){
		RBNode y = x.left;
		x.left = y.right;
		if (y.right != RBNode.nil)
			y.right.parent = x;
		y.parent = x.parent;
		if (x.parent == RBNode.nil)
			root = y;
		else {
			if (x == x.parent.right)
				x.parent.right = y;
			else
				x.parent.left = y;
		}
		y.right = x;
		x.parent = y;
	}
	  
	/**
	 * A rotation changes the structure of the tree without changing the in-order order of the 
	 * sequence of values that it stores. 
	 * 
	 * @param: x: node which must be rotated
	 * @preconditions: x != NIL and x.right != NIL
	 * @postconditions: this tree is a valid red-black tree
	 * 
	 */
	private void LeftRotate(RBNode x) {
		RBNode y = x.right;
		x.right = y.left;
	   
		if (y.left != RBNode.nil)
			y.left.parent = x;
		y.parent = x.parent;
		if (x.parent == RBNode.nil)
			root = y;
		else {
			if (x == x.parent.left)
				x.parent.left = y;
			else
				x.parent.right = y;
		}
		y.left = x;
		x.parent = y;
	}	
	
	  
	  /**
	   * public void delete(int i)
	   * 
	   * 
	   * We begin by finding the node to be deleted with search() 
	   * and deleting it as we would in a binary search tree. 
	   * we're using deleteFixUp() to keep this tree valid
	   * 
	   * @param: key: this method deletes the node with this key 
	   * @precondition:  none
	   * @postcondition: contains(i) == false (that is, i is in the list)
	   */
	   public void delete(int key) {
		   RBNode x= new RBNode();
		   RBNode y= new RBNode();
		   RBNode z = Search(key);
		   if (z == RBNode.nil){
			   return;// steps;
		   }
		   if (z.left == RBNode.nil|| z.right == RBNode.nil){
			   y = z;
		   }else{
			   y = suc(z);
		   }
		   if (y.left != RBNode.nil){
			   x = y.left;
		   }else{
			   x = y.right;
		   }
		   x.parent = y.parent;
		   if (y.parent == RBNode.nil){
			 root = x;  
		   }else if (y==y.parent.left){
			   y.parent.left = x;
		   }else{
			   y.parent.right = x;
		   }
		   if (!y.equals(z)){
			   z.key = y.key;
		   }
		   if (y.color == Color.BLACK){
			   deleteFixup (x);
		   }
		   size--;
	   }
	   
	   /**
	    * private RBNode suc(RBNode x)
	    * 
	    * Return x successor, node that's key is the next(greater) than x.key
	    * 
		* @param: x - RBNode, algorithm find the most closely greater node.key to x.key
	    * @preconditions: x != null
	    * @return such node that node.key > x.key most closely.
	    * 	If x.key is the greatest in the tree ==> @return NIL
	    */
	   private RBNode suc(RBNode x) {
		   if (x.right != RBNode.nil){
			   return minimum(x.right);
		   }
		   RBNode y = x.parent;
		   while (y != RBNode.nil && x==y.right){
			   x = y;
			   y = y.parent;
		   }
		   return y;
	}
	   
	   /**
		 * this method keeps the tree valid after deletion by going over all cases
		 */
		private int deleteFixup(RBNode x) {	   
			int steps = 0;
			RBNode w = new RBNode();
			while(x!=root && x.color == Color.BLACK) {
				if(x==x.parent.left){
				   w = x.parent.right;
				   if (w.color == Color.RED) {
					   w.color = Color.BLACK;
					   x.parent.color = Color.RED;
					   LeftRotate(x.parent);
					   steps++; //counter for rotate
					   w = x.parent.right;
					   steps++; //counter for coloring
				   }
				   if(w.left.color == Color.BLACK && w.right.color == Color.BLACK) {
					   w.color = Color.RED;   //w.left.color = "red";
					   steps++; //counter
					   x = x.parent;
				   }
				   else {
					   if(w.right.color == Color.BLACK) {
						   w.left.color = Color.BLACK;
						   w.color = Color.RED;
						   RightRotate(w);
						   steps++; //counter for rotate
						   w = x.parent.right;
						   steps++; //counter for coloring
					   }
				       w.color = x.parent.color;
					   x.parent.color = Color.BLACK;
					   w.right.color = Color.BLACK;
					   LeftRotate(x.parent);  //LeftRotate(x);
					   steps++; //counter for rotate
					   x = root;
					   steps++; //counter for coloring
				   }
			   }	
			   else {
				   w = x.parent.left;
				   if (w.color == Color.RED) {
					   w.color = Color.BLACK;
					   x.parent.color = Color.RED;
					   RightRotate(x.parent);
					   steps++; //counter for rotate
					   w = x.parent.left;
					   steps++; //counter for coloring
				   }
				   if(w.right.color == Color.BLACK && w.left.color == Color.BLACK) {
					   w.color = Color.RED;
					   steps++; //counter
					   x = x.parent;
				   }
				   else { 
					   	if(w.left.color == Color.BLACK) {
					   		w.right.color = Color.BLACK;
					   		w.color = Color.RED;
					   		LeftRotate(w);
					   		steps++; //counter for rotate
					   		w = x.parent.left;
					   		steps++; //counter for coloring
					   	}
					   	w.color = x.parent.color;
					    x.parent.color = Color.BLACK;
					    w.left.color = Color.BLACK;
					    RightRotate(x.parent);
					    steps++; //counter for rotate
					    x = root;
					    steps++; //counter for coloring
				   }
			   }
			}
			x.color = Color.BLACK;
			steps++; //counter
			return steps;
		}
		
	/**
	 * Returns node that has the smallest key. If the tree is empty return Nil node
	 *  
	 * @param x- node from which to start searching minimum.
	 * @return If !x.empty() @return node with minimal key, else @return NIL node
	 * 						(minimum in the tree x could be x itself)
	 */
	private RBNode minimum(RBNode x) {
		while (x.left != RBNode.nil && x.left!=null)
			x = x.left;
		return x;
	}
	/**
	 * Returns node that has the largest key. If the tree is empty return Nil node
	 * 
	 * @param x - node from which to start searching maximum.
	 * @return If !x.empty() @return node with maximal key, else return NIL node
	 * 				(maximum in the tree x could be x itself)
	 * 
	 */
	private RBNode maximum(RBNode x) {
		while (x.right != RBNode.nil && x.right!=null){
			x = x.right;
		}
		return x;
	}
	
   /**
    * public int min()
    *  
    * Returns the smallest key in the tree. If the tree
    * is empty, returns -1;
    * 
    * @precondition: none
    * @postcondition: if this tree.empty() then @return -1, else @return minimum key;
    */
   public int min()
   {
	   return minimum(root).key; 
   }
   
   /**
    * public int max()
    * 
    * Returns the largest key in the tree. If the tree
    * is empty, returns -1;
    * 
    * precondition: none
    * postcondition: if this tree.empty() then @return -1, else @return maximum key;
    */
   public int max()
   {
	   return maximum(root).key; 
   }
   
  /**
   * public int[] toIntArray()
   * 
   * returns an int[] array containing the values stored in the tree,
   * in ascending order.
   * 
   * preconditions: none
   * postconditions: returns an array containing exactly the tree's elements in
   *                 ascending order.
   */
  public int[] toIntArray()
  {
	 
		int[] arr = new int[size];
		i = 0;
		toArray(root, arr);
		return arr;
  }
  
  /**
  * method that recursively copies RBTree keys in in-order order to array
  * 
  * @param root- node, RBTree root from where to put key to arr
  * @param arr- array[size], empty array
  * @post arr- contains exactly the tree's elements in ascending order.
  * 
  */
 private void toArray(RBNode root, int [] arr) {
	 	if (root == RBNode.nil || root.key == -1)
	 		return;

	 	toArray(root.left, arr);
	 	arr[i++] = root.key;
	
	 	toArray(root.right, arr);
 }
 
 /**
  * public boolean isValid()
  *
  * Returns true if and only if the tree is a valid red-black tree.
  *
  * precondition: none
  * postcondition: none
  *   
  */
  public boolean isValid() 
  {
	  return root.isBinaryTree() && root.hasRedBlackRules();
  }


 /**
  * public int maxDepth()
  * 
  * Returns the maximum depth of a node in the tree. If the tree
  * is empty, returns -1;
  * 
  * precondition: none
  * postcondition: none
  */
 public int maxDepth()
 {
	 if (empty()) return -1;
	 return root.maxDepth();
 }

 /**
  * public int minLeafDepth()
  * 
  * Returns the minimum depth of a leaf in the tree. If the tree
  * is empty, returns -1;
  * 
  * precondition: none
  * postcondition: none
  */
 public int minLeafDepth()
 {
	 if (empty()) return -1;
	 return root.minDepth(); 
 }

   /**
    * public int size()
    * 
    * Returns the number of nodes in the tree.
    * 
    * precondition: none
    */
   public int size()
   {
	   return size; 
   }
   
  /**
   * public class RBNode
   * 
   * If you wish to implement classes other than RBTree
   * (for example RBNode), do it in this file, not in 
   * another file 
   *  
   */
   
  public static class RBNode{
	  	public static final RBNode nil = new RBNode();// Static NIL node
		static {
			nil.parent = nil.left = nil.right = nil;
		}

		public int key; // Value in node
		public RBNode left; // Left child of node
		public RBNode right; // Right child of node
		public RBNode parent; // Parent of node
		public Color color; // Color of node

		/**
		 * RBNode constructor Construct new node with value key and at black
		 * color
		 * 
		 * @param key
		 *            - value of node
		 */
		public RBNode(int key) {
			this.key = key;
			this.left = nil;
			this.right = nil;
			this.parent = nil;
			this.color = Color.BLACK;
		}
		
		/**
		 * @return true iff 'this' has properties 1-5 of a red black tree:
		 * 			1. Every node is either red or black
		 * 			2. The root is black
		 * 			3. Every leaf is black.
		 * 			4. If a node is red then both its children are black
		 * 			5. For each node, all simple paths from the node to
		 * 			   descendant leaves contain the same number of black nodes
		 * 
		 * 		Note that 'this' will be treated as the root.
		 */
		public boolean hasRedBlackRules() {
			return this.hasRedBlackRules_rec(-1)>=0;
		}

		/**
		 * @param curr_black_height the current black height.
		 * 							If 'this' should be treated as root
		 * 							then this should be set to -1
		 * @return a positive number iff 'this' has properties 1-5 of a red black tree:
		 * 			1. Every node is either red or black
		 * 			2. The root is black
		 * 			3. Every leaf is black.
		 * 			4. If a node is red then both its children are black
		 * 			5. For each node, all simple paths from the node to
		 * 			   descendant leaves contain the same number of black nodes
		 * 			if 'this' is a leaf then the positive number is the black height of the leaf
		 */
		private int hasRedBlackRules_rec(int curr_black_height) {
			//check self:
			
			//check color is red or black
			if (this.color!=Color.RED && this.color!=Color.BLACK)
				return -1;
			
			//check if root then black
			if (curr_black_height==-1 && this.color!=Color.BLACK)
				return -1;
			
			//check if leaf->black and return black height
			if (this==nil) { //nils are used as leaves
				if (this.color!=Color.BLACK) {
					return -1;
				} else {
					return curr_black_height+1; //black, then +1
				}
			}
			
			//check own color and children colors
			if (this.color==Color.RED) {
				if (left.color!=Color.BLACK || right.color!=Color.BLACK)
					return -1;
			}
			
			//check children including passing +1 if black
			if (this.color==Color.BLACK)
				++curr_black_height;
			
			int result_left = left.hasRedBlackRules_rec(curr_black_height);
			int result_right = right.hasRedBlackRules_rec(curr_black_height);
			
			if (result_left==-1 || result_right==-1 || result_left!=result_right)
				return -1;
			
			return result_left; //should be the same as returning result_right
		}

		public boolean isBinaryTree() {
			boolean flgLeft = true;
			boolean flgRight = true;
			
			if (left!=nil) {
				flgLeft=(left.key<=this.key && left.isBinaryTree());
			}
			
			if (right!=nil) {
				flgRight=(right.key>=this.key && right.isBinaryTree());
			}
			
			return flgLeft && flgRight;
		}

		/**
		 * RBNode constructor Construct NIL node at black color
		 */
		private RBNode() {
			this.key = -1;
			left = null;
			right = null;
			parent = null;
			color = Color.BLACK;
		}
		
		public int minDepth() {
			if (this==nil) //if a leaf
				return 0;
			
			final int left_depth = left.minDepth();
			final int right_depth = right.minDepth();
			
			return Math.min(left_depth, right_depth) + 1;
		}
		
		public int maxDepth() {
			if (this==nil) //if a leaf
				return 0;
			
			final int left_depth = left.maxDepth();
			final int right_depth = right.maxDepth();
			
			return Math.max(left_depth, right_depth) + 1;
		}
	}
	
	/**
	 * Color enumerator
	 */
	private enum Color {
		RED, BLACK;
	}
	
  
  /**
 * @original author Shai Balsiano(037018009, shaibela) and Maayan Keshet (300749736, maayanke)
 * email addresses: Shay: hershalle@gmail.com, Maayan: maayan@maayank.com
 * Modified for semester 2011/2012 a
 */

}
  
